class Heap {
    constructor(min=true) {
        this.min = min;
        this.arr = [];
    }
    _up(offset, newVal) {
		let parent = parseInt((offset - 1) / 2);
		while (parent >= 0 && offset>0)
		{
			if (this.min)
			{
				if (this.arr[parent] <= newVal)
					break;
			}
			else
			{
				if (this.arr[parent] >= newVal)
					break;
			}

            this.arr[offset] = this.arr[parent];
            offset = parent;
            parent = parseInt((offset - 1) / 2);
		}
		this.arr[offset] = newVal;
    }
    _down(offset)
	{
		let n = this.arr.length;
		let child = parseInt(2 * offset + 1);
		let tmp = this.arr[offset];
		while (child < n)
		{
			if (child + 1 < n)//找最大或最小子节点
			{
				if (this.min)
				{
					if (this.arr[child] > this.arr[child + 1])
						child++;
				}
				else
				{
					if (this.arr[child] < this.arr[child + 1])
						child++;
				}
			}
			if (this.min)
			{
				if (this.arr[child] >= tmp)
					break;
			}
			else
			{
				if (this.arr[child] <= tmp)
					break;
			}

				this.arr[offset] = this.arr[child];
				offset = child;
				child = parseInt(2 * offset + 1);
		}
		this.arr[offset] = tmp;
    }
    //入堆
    push(val) {
        if (this.arr.length==0)
		{
			this.arr.push(val);
		}
		else
		{
			this._up(this.arr.length, val);
		}
    }
    //出堆
    pop() {
		if (this.arr.length==1)
		{
			this.arr.length = 0;
		}
		else if (this.arr.length>1)
		{
			this.arr[0] = this.arr[this.arr.length-1];
			this._down(0);
			this.arr.length--;
		}
    }
    //堆顶元素
    top () {
        return this.arr[0];
    }
    //数量
    count() {
        return this.arr.length;
    }
    //检查堆完整性
    checkHeap()
	{
		for (let i = 1; i < this.arr.length; ++i)
		{
			let p = parseInt((i - 1) / 2);
			if (this.min)
			{
				if (this.arr[p] > this.arr[i])
				{
					return false;
				}
			}
			else
			{
				if (this.arr[p] < this.arr[i])
				{
					return false;
				}
			}
		}
		return true;
	}
}

// let arr = [544,375,981,35,30,977,269,683,922,299,56,321,394,825,996,454,751,121,41,5,68,673,519,276,665,163,807,376,439,698,329,817,656,208,312,18,391,106,731,95];
// let heap = new Heap();
// for (let i = 0; i < arr.length; i++) {
//     heap.push(arr[i]);
// }
// console.log(heap.arr);
// console.log(heap.checkHeap());
// for (let i = 0; i < 30; i++) {
//     heap.pop();
// }
// console.log(heap.checkHeap());

module.exports = Heap;